#pragma once
#include<iostream>
#include<vector>

using namespace std;

class Date
{
public:
	Date(int year = 1900, int month = 1, int day = 1)
		: _year(year)
		, _month(month)
		, _day(day)
	{}
	bool operator<(const Date& d)const
	{
		return (_year < d._year) ||
			(_year == d._year && _month < d._month) ||
			(_year == d._year && _month == d._month && _day < d._day);
	}
	bool operator>(const Date& d)const
	{
		return (_year > d._year) ||
			(_year == d._year && _month > d._month) ||
			(_year == d._year && _month == d._month && _day > d._day);
	}
	bool operator!=(const Date& d)const
	{
		return _year != d._year && _month != d._month && _day != d._day;
	}
	friend ostream& operator<<(ostream& _cout, const Date& d);
private:
	int _year;
	int _month;
	int _day;
};

ostream& operator<<(ostream& _cout, const Date& d)
{
	_cout << d._year << "-" << d._month << "-" << d._day;
	return _cout;
}


namespace cyq
{
	template<class T>
	class Less
	{
	public:
		bool operator()(const T& x, const T& y)
		{
			return x < y;
		}
	};

	template<class T>
	class Greater
	{
	public:
		bool operator()(const T& x, const T& y)
		{
			return x > y;
		}
	};

	template<class T>
	class LessDate
	{
	public:
		bool operator()(const T& x, const T& y)
		{
			return *x < *y;
		}
	};

	//类模板的全特化
	template<>
	class Less<Date*>
	{
	public:
		bool operator()(Date* x,  Date* y)
		{
			return *x < *y;
		}
	};

	template<class T,class container=vector<T>,class compare=Less<T>>
	class priority_queue
	{
		void AdjustDown(int parent)
		{
			compare com;
			int child = 2 * parent + 1;
			//找左右孩子大的那一个
			if (child + 1 < _con.size() && com(_con[child], _con[child + 1]))
			{
				child++;
			}
			while (child < _con.size())
			{
				if (com(_con[parent], _con[child]))
				{
					std::swap(_con[parent], _con[child]);
					parent = child;
					child = 2 * parent + 1;
				}
				else
					break;
			}
		}

		void AdjustUp(int child)
		{
			compare com;
			int parent = (child - 1) / 2;

			while (child > 0)
			{
				if (com(_con[parent], _con[child]))
				{
					std::swap(_con[parent], _con[child]);
					child = parent;
					parent = (child - 1) / 2;
				}
				else
					break;
			}
		}

	public:
		priority_queue()
		{}

		//用迭代区间构造
		template<class InputIterator>
		priority_queue(InputIterator first, InputIterator last)
		{
			while (first != last)
			{
				_con.push_back(*first);
				first++;
			}

			//向下调整建堆
			for (size_t i = (_con.size() - 1 - 1) / 2; i >= 0; i--)
			{
				AdjustDown(i);
			}
		}

		void push(const T& x = T())
		{
			_con.push_back(x);
			AdjustUp(_con.size() - 1);

		}

		void pop()
		{
			std::swap(_con[0], _con[_con.size() - 1]);
			_con.pop_back();

			AdjustDown(0);
		}

		size_t size()
		{
			return _con.size();
		}

		bool empty()
		{
			return _con.empty();
		}

		T& top()
		{
			return _con.front();
		}


		
	private:
		container _con;
	};
}
